import { Node } from "../singleLinkList";

/**
 * 反转链表(迭代)
 * @param head
 */
export const reverseIterator = <T>(head: Node<T> | null) => {
    // 边界判断
    if (head === null || head.next === null) return head;

    let newHead: Node<T> | null = null
    while(head !== null) {
        // 保存head.next
        const prev: Node<T> | null = head.next;

        head.next = newHead;
        newHead = head;
        
        // 新的头节点为原来的下一个
        head = prev;
    }

    return newHead;
}

/**
 * 反转链表(递归)
 * @param head 
 */
export const reverse = <T>(head: Node<T> | null): Node<T> | null => {
    // 边界判断
    if (head === null || head.next === null) return head;

    // 找到最后的节点 
    const newHead = reverse(head.next)
    
    // 调整当前的head
    head.next.next = head;

    // 清空自己的next
    head.next = null

    return newHead;
}